package offerbook.Code25_pathInBT;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
 * 这条路径上所有节点值相加等于目标和。【leetcode112】
 * @date 2020/3/9 19:08
 */
public class Code05_FindSumInAllPath2_leetcode113 {
    public static void preInOder(TreeNode treeNode, int target,
                                 List<List<Integer>> totalPath, List<Integer> path) {
        if (treeNode == null) {
            return;
        }
        target -= treeNode.val;
        //前序遍历要处理的当前节点,先添加当前节点
        path.add(treeNode.val);
        //如果是叶子节点，并且满足和
        if (treeNode.left == null && treeNode.right == null && target == 0) {
            //要开启新的点
            totalPath.add(new ArrayList<>(path));
        }
        preInOder(treeNode.left, target, totalPath, path);
        preInOder(treeNode.right, target, totalPath, path);
        //返回上一级，要删除当前节点
        path.remove(path.size() - 1);
    }


}
